package test;

import dq.node.List;
import dq.node.ListNode;

/**
 * @Author: Dang Qi
 * @Date: 2021/4/18  21:01
 * @Description:
 */
public class Tencent2 {
    public static void main(String[] args) {
        int[] a = {1,2,3,1,2,4};
        ListNode head = List.newList(a);
        ListNode n = move(head);
        List.showList(n);
    }
    public static ListNode move(ListNode head){
        if(head==null) return null;
        ListNode tmp = head;
        int len=0;
        while(tmp!=null && (++len)>=0) tmp = tmp.next;
        ListNode[] nodes = new ListNode[len];
        nodes[0] = head;
        for(int i = 1; i < len; i++){
            nodes[i] = nodes[i-1].next;
        }
        int i=0, j=1, k=0;
        while(i < len && j < len && k < len) {
            int t=nodes[(i+k)%len].val-nodes[(j+k)%len].val;
            if(t==0) k++;
            else {
                if(t>0){
                    i = Math.max(i+k+1, j);
                    j = i + 1;
                }
                else j= j + k +1;
                k = 0;
            }
        }
        nodes[len-1].next = head;
        nodes[(i-1+len)%len].next = null;
        return nodes[i];
    }
}
